package 剑指Offer.medium;

public class 礼物的最大价值 {

    class Solution {
        public int maxValue(int[][] grid) {
            if (grid == null || grid.length == 0) return 0;
            int rowSize = grid.length;
            int colSize = grid[0].length;
            for (int i = 1; i < colSize; i++) {
                grid[0][i] += grid[0][i - 1];
            }
            for (int i = 1; i < rowSize; i++) {
                grid[i][0] += grid[i - 1][0];
            }
            for (int i = 1; i < rowSize; i++) {
                for (int j = 1; j < colSize; j++) {
                    grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
                }
            }
            return grid[rowSize - 1][colSize - 1];
        }
    }
}
